package test;

public class test {
    public static void main(String[] args) {
        System.out.println(strStr("125161294334","125181291"));
    }
public static int strStr(String hasStack,String needle) {
    int n = hasStack.length();
    int m = needle.length();
    if (m == 0) {
        return 0;
    }
    int[] arr = new int[m];
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
            j = arr[j - 1];
        }
        if (needle.charAt(i) == needle.charAt(j)) {
            j++;
        }
        arr[i] = j;
    }
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && hasStack.charAt(i) != needle.charAt(j)) {
            j = arr[j - 1];
        }
        if (hasStack.charAt(i) == needle.charAt(j)) {
            j++;
        }
        if (m == j) {
            return i - m + 1;
        }
    }
    return -1;
}}
